# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
        result=[]
        route=[]
        if K==0:
            return [target.val]
        def search(node):
            nonlocal target
            if not node:
                return False
            if node==target:
                return True
            else:
                route.append(node)
                if search(node.left) or search(node.right):
                    return True
                else:
                    route.pop()
                    return False 
        search(root)
        result=[]
        def find(node,dist):
            nonlocal target
            if not node:
                return 
            if node==target:
                return 
            if dist==0:
                result.append(node.val)
                return 
            else:
                find(node.left,dist-1)
                find(node.right,dist-1)
        n=len(route)
        i=0
        if n!=0:
            while i<n-1:
                if K-n+i>0:
                    if route[i].left and route[i].left.val!=route[i+1].val:
                        find(route[i].left,K-n+i-1)
                    if route[i].right and route[i].right.val!=route[i+1].val:
                        find(route[i].right,K-n+i-1)
                elif K-n+i==0:
                    result.append(route[i].val)
                i+=1
            find(route[i],K-1)
        find(target.left,K-1)
        find(target.right,K-1)
        return result

'''
执行用时：
40 ms
, 在所有 Python3 提交中击败了
91.12%
的用户
内存消耗：
15.2 MB
, 在所有 Python3 提交中击败了
42.16%
的用户
'''